<
theory> A branch of mathematics introduced by Dana Scott in
1970 as a mathematical
theory of programming languages, and
for nearly a quarter of a century developed almost exclusively
in connection with
denotational semantics in computer
science.
In
denotational semantics of programming languages, the
meaning of a program is taken to be an element of a
domain. A
domain is a mathematical structure consisting of a set of
values (or "points") and an ordering relation, <= on those
values.
Domain theory is the study of such structures.
("<=" is written in
LaTeX as
subseteq)
Different domains correspond to the different types of object
with which a program deals. In a language containing
functions, we might have a
domain X -> Y which is the set of
functions from
domain X to
domain Y with the ordering f <= g
iff for all x in X, f x <= g x. In the
pure lambda-calculus
all objects are functions or
applications of functions to
other functions. To represent the meaning of such programs,
we must solve the
recursive equation over domains,
D = D -> D
which states that
domain D is (
isomorphic to) some {function
space} from D to itself. I.e. it is a
fixed point D = F(D)
for some operator F that takes a
domain D to D -> D. The
equivalent equation has no non-trivial solution in {set
theory}.
There are many definitions of domains, with different
properties and suitable for different purposes. One commonly
used definition is that of Scott domains, often simply called
domains, which are
omega-algebraic,
consistently complete
CPOs.
There are
domain-theoretic computational models in other
branches of mathematics including
dynamical systems,
fractals,
measure theory,
integration theory,
probability theory, and
stochastic processes.
See also
abstract interpretation,
bottom, {pointed
domain}.
(1999-12-09)